This invention relates generally to an encoding method and apparatus, a decoding method and apparatus and recording medium, and more particularly to an encoding method and apparatus, a decoding method and apparatus and a recording medium usable in a system for high efficiency picture encoding or decoding for efficient picture transmission or storage.
The International Organization for Standardization (ISO) has promulgated a standardized system for a conventional picture compression system called Joint Photographic Expert Group (JPEG). This system provides optimal encoding or decoding of pictures by applying a Discrete Cosine Transformation (DCT) to an image to transform that image into DCT coefficients. This system works most efficiently when a relatively large number of bits are to be employed to represent the encoded information. However, if the number of bits to be employed to represent the encoded information is less than a certain predetermined value, block distortion inherent in such a DCT transform becomes prevalent enough to deteriorate the quality of the picture which may be noticed by a viewer.
In response to these deficiencies of the JPEG and DCT procedure, a new Iterated Function System (IFS) picture compression technique has been proposed, and is beginning to gain favor. This IFS technique exploits self-similarity between portions of pictures and is based on fractal geometry. IFS works on the assumption that various portions of a particular picture are analogous, even though they may be of a different size, position, perspective, or orientation. IFS utilizes this redundancy in pictures to efficiently encode the picture without resulting block distortion, as may be generated in the JPEG system. Therefore, IFS is not nearly as dependent upon the number of bits to be used to represent the encoded information, and therefore the resolution during decoding does not suffer when a relatively smaller number of bits are to be used to represent the encoded information.
The basic structure of IFS is set forth in Arnaud E. Jaquin""s thesis entitled xe2x80x9cImage Coding Based on a Fractal Theory of Iterated Contractive Image Transformationsxe2x80x9d, IEEE Transactions on Image Processing, Vol. 1, No. 1, pp. 18-30), and is further set forth in U.S. Pat. Nos. 5,347,600; 5,065,447 and 4,941,193, all issued to Barnsley et al. The encoding and decoding devices as generally set forth in these references will now be described with reference to prior art FIGS. 19 and 20.
Referring first to FIG. 19, the operation of an encoding device according to the prior art is shown. As is set forth in FIG. 19, an original picture 300 is entered to a block generating circuit 200 and is therein split into a plurality of blocks 301. All of blocks 301 together cover the entire original picture 300, but do not overlap with each other. Original picture 300 is also forwarded to reduced picture generating circuit 202 which produces a picture 307 having a reduced size, such as by way of a reduction scheme known in the art. The reduced picture is forwarded to and stored within reduced picture storage circuit 204.
Each of blocks 301 is forwarded to a proximate area search circuit 201 which searches reduced size picture 307 stored in reduced picture storage circuit 204 to determine whether any portions of the reduced size picture are analogous to the particular block 301 being searched. As noted above, this search includes searching for portions of reduced size picture 307 which are of different size, position, perspective, or orientation than the block 301 being searched. In accordance with the detected result indicating a successful search for a most similar portion, similar block position information 306, which specifies the position of the selected portion 305 within the reduced size picture 307, is transmitted to reduced picture storage circuit 204. In accordance with this indicated result, selected portion 305 of the reduced size picture 307 stored within reduced picture storage circuit 204 is extracted, and is transmitted to a rotation/inversion/level value conversion circuit 203.
Rotation/inversion/level value conversion circuit 203 processes portion 305 of reduced size picture 307 by a rotation/inversion/level value transformation in accordance with transformation parameters 304 which are supplied from proximate area search circuit 201. These transformation parameters 304 are indicative of the transformation which must be performed on selected portion 305 of reduced size picture 307 in order to transform that selected portion into block 301. These parameters are determined when a particular portion 305 of reduced size picture 307 is found to most closely correspond to block 301 being searched. Upon transformation by rotation/inversion/level value conversion circuit 203, a transform reduced-size picture 303 is forwarded to proximate area search circuit 201. There as a result, transformation parameters 304 and similar block position information 306 are output as ISF codes 302. Thus, a first picture is input to the system, and the output includes at least transformation parameters, for transforming a first block of that first picture into a second similar block of a reduced size picture, and position information, for determining the position of the second block within the encoded picture.
Referring next to FIG. 20, a decoding apparatus is provided in which the IFS codes recorded on, for example, a disc 400, including transformation parameters and similar block position information 302 that are output by the encoding device of FIG. 19, are entered into and stored in an IFS code storage circuit 205. IFS codes 302 are then sequentially read out from IFS code storage circuit 205 for each block, and are forwarded to an IFS code read out circuit 206. IFS code read out circuit 206 divides the codes into similar block position information 306 and transformation parameters 304 as had been produced by the encoder. Similar block position information 306 is then forwarded to reduced picture storage circuit 204 in order to reproduce the area of the reduced-size picture specified by similar block position information 306. The portion 305 of the reduced size picture stored in reduced picture storage circuit 204 corresponding to the specified area is then transmitted to a rotation/inversion/level value conversion circuit 203, and is transformed in accordance with transformation parameters 304 which are supplied from IFS code read out circuit 206. The resulting transformed picture 303 forwarded from rotation/inversion/level conversion circuit 203 is stored within decoded picture storage circuit 208. This procedure is performed for each block in the picture for which IFS codes are provided.
After all of the IFS codes for all of the blocks have been read out, IFS read out circuit 206 sends a READ OUT END notification signal 310 to duplication control circuit 207. It is then determined by duplication control circuit 207 whether information for all blocks has been obtained. If not, a repeat command 309 is sent to IFS code read out circuit 206, the IFS codes 302 are input once again, and the procedure begins again. The information for all blocks has been read out, and decoding continues through a recursive decoding procedure. Duplication control circuit 207 counts the number of recursive decoding/duplicating operations that have been executed, and if this count has not reached a predetermined value, duplication control circuit 207 sends a reprocessing command signal 311 to a switch 209 in order to send partially decoded picture 313 to reduced picture generating circuit 202 via information path 314. Reduced picture generating circuit 202 generates a partially decoded reduced size picture 315 of decoded picture 313 in a manner similar to that as in the encoding device in order to re-write the contents of the picture stored in reduced picture storage circuit 204 and to enable a next recursive decoding step to start with partially decoded reduced picture 315. If the predetermined number of recursive decoding operations have taken place, and thus the duplicating operation has been carried out the predetermined number of times, a decoded picture output control signal is sent by reprocessing command signal 311 to switch 209 in order to couple a decoded picture 313 output from decoded picture storage circuit 208 to a picture output port 316. Decoded picture 313 comprises a conglomeration picture of all of the decoded blocks noted above after being recursively decoded for a predetermined number of iterations and is read out from decoded picture storage circuit 208 in accordance with control signal 312.
While this information encoding and decoding technique has been somewhat satisfactory, it has suffered from at least one major drawback which is evident when a user wishes to decode (or encode) only a portion of a picture. In the prior art technique described above, the degree of error between a certain range block to be encoded and each of a plurality of domain blocks located at arbitrary positions throughout an entire screen picture is measured, and the domain block resulting in the smallest error, therefore being the most similar block, is selected. Thereafter, a transformed parameter and block position information are determined, and are provided as a code. A plurality of codes, one for each range block so that the range blocks comprise an entire picture, are then written into a bit stream in the order of these coded blocks.
In order to further improve encoding and transmission efficiency, and since the block size of the domain block may be variable, the words of the codes are coded in a variable length manner, i.e., variable length Huffman encoding or the like is applied to the code or codes, in order to form the bit stream. However, in these cases, if only a portion of a picture is to be decoded, it is necessary for the entire bit stream to be read out, beginning with header portion thereof, until the code corresponding to the predetermined area picture appears. Additionally, in order to decode just the desired portion of the picture, it is necessary for the entire picture to be decoded, since it is possible that the domain blocks associated with the desired range blocks may be positioned anywhere within the picture. Thus, the problem arises during high-speed processing in that a substantial portion of information which is unnecessary and unwanted may need to be decoded in order to decode a small portion of a picture as desired.
Therefore, it would be beneficial to provide an improved encoding apparatus and method that overcome the drawbacks of the prior art.
Accordingly, it is an object of the invention to provide an improved encoding and decoding apparatus and method.
A further object of the invention is to provide an improved encoding and decoding apparatus and method that allow for only a portion of an encoded picture to be decoded, as desired.
Another object of the invention is to provide an improved encoding and decoding apparatus and method in which a portion of a picture to be decoded may be extracted from a bit stream including encoded information for an entire picture without reading each portion of information in the bit stream.
A still further object of the invention is to provide a recording medium including all information for implementing an improved encoding and decoding method that allows for only a portion of an encoded picture to be decoded, as desired.
Yet another object of the invention is to provide a recording medium including all information for implementing an improved encoding and decoding method in which a portion of a picture to be decoded may be extracted from a bit stream including encoded information for an entire picture without reading each portion of information in the bit stream
Still other objects and advantages of the invention will in part be obvious and will in part be apparent from the specification and drawings.
Generally speaking, in accordance with the invention, improved IFS encoding and decoding techniques are provided. The encoding technique includes the step of splitting an input image into a plurality of first and second block portions. Transform processing is performed on each second block portion, and a determination is made as to which of the transformed block portions residing in the same predefined area of the input image as a preselected first block portion is most similar to that preselected first block portion. Block position information indicating the position of the selected second block portion and a transformation parameter representing the transform processing of that selected second block portion are output as a code.
The decoding technique in accordance with the invention allows for decoding from a code representing blocks from a predetermined area of an image. The received code includes block position information indicating a position in a particular area of a picture of a pretransformed block and a transformation parameter representing the transform processing of the pretransformed block. Processing of the block identified by the block position information and based on the transformation parameter within the predetermined area is performed recursively to reconstruct a predetermined area of the decoded picture from the transformation process blocks.
A recording medium is provided for storing a computer program for operation on a general purpose computer for implementing the encoding and decoding method in accordance with the invention, and for outputting a coded bit stream in the encoding case, and a decoded predetermined area of a coded picture in the decoding case.
The several steps and the relation of one or more of steps with respect to each of the others and the apparatus embodying features of construction, combinations of elements and arrangement of parts which are adapted to affect such steps, all as exemplified in the following detailed disclosure, and the scope of the invention will be indicated in the claims.